題目：20. Valid Parentheses

連結：https://leetcode.com/problems/valid-parentheses/description/

• 等級：Easy

解題思路

1. 利用stack紀錄括號起始與結束順序做比對

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<Character>();
        for (int i = 0 ; i < s.length();i++)
        {
            char c = s.charAt(i);
            if (c == '(')
                stack.push(')');
            else if (c == '{')
                stack.push('}');
            else if (c == '[')
                stack.push(']');
            else if (stack.isEmpty() || stack.pop() != c)
                return false;
        }
        if (stack.isEmpty())
            return true;
        else
            return false;
    }
}

• Time complexity: O(n)
• Space complexity: O(n)

題目：155. Min Stack

連結：https://leetcode.com/problems/valid-parentheses/description/

• 等級：Medium

解題思路

1. 利用stack並重新撰寫類別，而外而外紀錄最小值
2. 當push和pop時，如果為最小值要額外push和pop

class MinStack {

    private Stack<Integer> stack;
    private int min = Integer.MAX_VALUE;

    public MinStack() {
        stack = new Stack<Integer>();
    }
    
    public void push(int val) {      
        if (val <= min)
        {
            stack.push(min);
            min = val;
        }
        stack.push(val);
    }
    
    public void pop() {
        if (stack.pop() == min)
            min = stack.pop();
    }
    
    public int top() {
        return stack.peek();
    }
    
    public int getMin() {
        return min;
    }
}

• Time complexity: O(1)
• Space complexity: O(n)